<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(A卷,100分)- 机器人（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>现有一个机器人&#xff0c;可放置于 M × N 的网格中任意位置&#xff0c;每个网格包含一个非负整数编号&#xff0c;当相邻网格的数字编号差值的绝对值小于等于 1 时&#xff0c;机器人可以在网格间移动。</p> 
<p><br /><strong>问题&#xff1a;</strong> 求机器人可活动的最大范围对应的网格点数目。<br /><strong>说明&#xff1a;</strong>网格左上角坐标为 (0,0) ,右下角坐标为(m−1,n−1)&#xff0c;机器人只能在相邻网格间上下左右移动</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>第 1 行输入为 M 和 N &#xff0c; M 表示网格的行数 N 表示网格的列数<br /> 之后 M 行表示网格数值&#xff0c;每行 N 个数值&#xff08;数值大小用 k 表示&#xff09;&#xff0c;<br /> 数值间用单个空格分隔&#xff0c;行首行尾无多余空格。<br /> M、 N、 k 均为整数&#xff0c;且 1 ≤ M,N ≤ 150, 0 ≤ k ≤ 50</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>输出 1 行&#xff0c;包含 1 个数字&#xff0c;表示最大活动区域的网格点数目&#xff0c;<br /> 行首行尾无<strong>多余空格。</strong></p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">4 4<br /> 1 2 5 2<br /> 2 4 4 5<br /> 3 5 7 1<br /> 4 6 2 4</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">6</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"> <p><img alt="" height="199" src="https://img-blog.csdnimg.cn/0bdfa12c984f42069e2e2ec07a06bec9.png" width="207" /></p> <p> 图中绿色区域&#xff0c;相邻网格差值绝对值都小于等于 1 &#xff0c;且为最大区域&#xff0c;对应网格点数目为 6。</p> </td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题其实就是求最大的连通分量&#xff0c;相邻网格是否连通的规则如下</p> 
<blockquote> 
 <p>当相邻网格的数字编号差值的绝对值小于等于 1 时</p> 
</blockquote> 
<p></p> 
<p>因此&#xff0c;求解连通分量&#xff0c;我们可以使用并查集。关于并查集的知识&#xff0c;请看&#xff1a;<a href="https://blog.csdn.net/qfc_128220/article/details/127588130?ops_request_misc&#61;%257B%2522request%255Fid%2522%253A%2522166870829816800192212313%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&amp;request_id&#61;166870829816800192212313&amp;biz_id&#61;0&amp;utm_medium&#61;distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-1-127588130-null-null.nonecase&amp;utm_term&#61;%E5%8F%91%E5%B9%BF%E6%92%AD&amp;spm&#61;1018.2226.3001.4450" title="华为机试 - 发广播_伏城之外的博客-CSDN博客_服务器广播 华为机试">华为机试 - 发广播_伏城之外的博客-CSDN博客_服务器广播 华为机试</a></p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
let m, n;
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 1) {
    [m, n] &#61; lines[0].split(&#34; &#34;).map(Number);
  }

  if (m &amp;&amp; lines.length &#61;&#61;&#61; m &#43; 1) {
    lines.shift();
    const matrix &#61; lines.map((line) &#61;&gt; line.split(&#34; &#34;).map(Number));

    console.log(getResult(matrix, m, n));
    lines.length &#61; 0;
  }
});

function getResult(matrix, m, n) {
  const ufs &#61; new UnionFindSet(m * n);

  // 上下左右的偏移量
  const offset &#61; [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  for (let i &#61; 0; i &lt; m; i&#43;&#43;) {
    for (let j &#61; 0; j &lt; n; j&#43;&#43;) {
      // 注意下面这层for是常量级的&#xff0c;就四次循环&#xff0c;因此&#xff0c;这里的时间复杂度还是O(n*m)&#xff0c;即
      for (let k &#61; 0; k &lt; offset.length; k&#43;&#43;) {
        const [offsetX, offsetY] &#61; offset[k];
        const newI &#61; i &#43; offsetX;
        const newJ &#61; j &#43; offsetY;
        if (newI &lt; 0 || newI &gt;&#61; m || newJ &lt; 0 || newJ &gt;&#61; n) continue;
        if (Math.abs(matrix[i][j] - matrix[newI][newJ]) &lt;&#61; 1) {
          ufs.union(i * n &#43; j, newI * n &#43; newJ);
        }
      }
    }
  }

  let total &#61; m * n;

  // ufs.count是连通分量的个数&#xff0c;如果只有一个连通分量&#xff0c;那么代表所有的点都可达
  if (ufs.count &#61;&#61;&#61; 1) return total;

  // 这个for循环是有必要的&#xff0c;确保每个点都指向祖先
  for (let i &#61; 0; i &lt; total; i&#43;&#43;) {
    ufs.find(i);
  }

  // 统计指向同一个祖先下点的个数&#xff0c;即每个连通分量下的点个数
  const countObj &#61; ufs.fa.reduce((p, c) &#61;&gt; {
    p[c] ? p[c]&#43;&#43; : (p[c] &#61; 1);
    return p;
  }, {});

  // 取最大个数
  return Math.max.apply(null, Object.values(countObj));
}

class UnionFindSet {
  constructor(n) {
    this.fa &#61; new Array(n).fill(0).map((_, i) &#61;&gt; i);
    this.count &#61; n;
  }

  find(x) {
    if (x !&#61;&#61; this.fa[x]) {
      return (this.fa[x] &#61; this.find(this.fa[x]));
    }
    return x;
  }

  union(x, y) {
    const x_fa &#61; this.find(x);
    const y_fa &#61; this.find(y);

    if (x_fa !&#61;&#61; y_fa) {
      this.fa[y_fa] &#61; x_fa;
      this.count--;
    }
  }
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.HashMap;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int m &#61; sc.nextInt();
    int n &#61; sc.nextInt();

    int[][] matrix &#61; new int[m][n];
    for (int i &#61; 0; i &lt; m; i&#43;&#43;) {
      for (int j &#61; 0; j &lt; n; j&#43;&#43;) {
        matrix[i][j] &#61; sc.nextInt();
      }
    }

    System.out.println(getResult(matrix, m, n));
  }

  public static int getResult(int[][] matrix, int m, int n) {
    UnionFindSet ufs &#61; new UnionFindSet(m * n);

    // 上下左右的偏移量
    int[][] offsets &#61; {<!-- -->{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    for (int i &#61; 0; i &lt; m; i&#43;&#43;) {
      for (int j &#61; 0; j &lt; n; j&#43;&#43;) {
        // 注意下面这层for是常量级的&#xff0c;就四次循环&#xff0c;因此&#xff0c;这里的时间复杂度还是O(n*m)&#xff0c;即
        for (int[] offset : offsets) {
          int newI &#61; i &#43; offset[0];
          int newJ &#61; j &#43; offset[1];

          if (newI &lt; 0 || newI &gt;&#61; m || newJ &lt; 0 || newJ &gt;&#61; n) continue;
          // 当相邻网格的数字编号差值的绝对值小于等于 1 时&#xff0c;机器人可以在网格间移动&#xff0c;即表示网格连通&#xff0c;可以合并
          if (Math.abs(matrix[i][j] - matrix[newI][newJ]) &lt;&#61; 1) {
            ufs.union(i * n &#43; j, newI * n &#43; newJ);
          }
        }
      }
    }

    int total &#61; m * n;

    // ufs.count是连通分量的个数&#xff0c;如果只有一个连通分量&#xff0c;那么代表所有的点都可达
    if (ufs.count &#61;&#61; 1) return total;

    // 这个for循环是有必要的&#xff0c;确保每个点都指向祖先
    for (int i &#61; 0; i &lt; total; i&#43;&#43;) {
      ufs.find(i);
    }

    // 统计指向同一个祖先下点的个数&#xff0c;即每个连通分量下的点个数
    HashMap&lt;Integer, Integer&gt; count &#61; new HashMap&lt;&gt;();
    for (int i : ufs.fa) {
      count.put(i, count.getOrDefault(i, 0) &#43; 1);
    }

    // 取最大个数&#xff0c;这里必然有值&#xff0c;因此不需要在get前判空
    return count.values().stream().max((a, b) -&gt; a - b).get();
  }
}

// 并查集
class UnionFindSet {
  int[] fa;
  int count;

  public UnionFindSet(int n) {
    this.fa &#61; new int[n];
    this.count &#61; n;
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) this.fa[i] &#61; i;
  }

  public int find(int x) {
    if (x !&#61; this.fa[x]) {
      return (this.fa[x] &#61; this.find(this.fa[x]));
    }
    return x;
  }

  public void union(int x, int y) {
    int x_fa &#61; this.find(x);
    int y_fa &#61; this.find(y);

    if (x_fa !&#61; y_fa) {
      this.fa[y_fa] &#61; x_fa;
      this.count--;
    }
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 并查集
class UnionFindSet:
    def __init__(self, n):
        self.fa &#61; [idx for idx in range(n)]
        self.count &#61; n

    def find(self, x):
        if x !&#61; self.fa[x]:
            self.fa[x] &#61; self.find(self.fa[x])
            return self.fa[x]
        return x

    def union(self, x, y):
        x_fa &#61; self.find(x)
        y_fa &#61; self.find(y)

        if x_fa !&#61; y_fa:
            self.fa[y_fa] &#61; x_fa
            self.count -&#61; 1


m, n &#61; map(int, input().split())

matrix &#61; []
for i in range(m):
    matrix.append(list(map(int, input().split())))

ufs &#61; UnionFindSet(m * n)

# 上下左右的偏移量
offsets &#61; ((-1, 0), (1, 0), (0, -1), (0, 1))

for i in range(m):
    for j in range(n):
        # 注意下面这层for是常量级的&#xff0c;就四次循环&#xff0c;因此&#xff0c;这里的时间复杂度还是O(n*m)&#xff0c;即
        for offsetX, offsetY in offsets:
            newI &#61; i &#43; offsetX
            newJ &#61; j &#43; offsetY

            if 0 &lt;&#61; newI &lt; m and 0 &lt;&#61; newJ &lt; n and abs(matrix[i][j] - matrix[newI][newJ]) &lt;&#61; 1:
                ufs.union(i * n &#43; j, newI * n &#43; newJ)

total &#61; m * n

# ufs.count是连通分量的个数&#xff0c;如果只有一个连通分量&#xff0c;那么代表所有的点都可达
if ufs.count &#61;&#61; 1:
    print(total)
else:
    # count字典用于统计指向同一个祖先下点的个数&#xff0c;即每个连通分量下的点个数
    count &#61; {}

    # 这个for循环是有必要的&#xff0c;确保每个点都指向祖先
    for i in range(total):
        ufs.find(i)
        fa &#61; ufs.fa[i]
        count[fa] &#61; count.get(fa, 0) &#43; 1

    # 取最大个数
    print(max(count.values()))

</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>